import java.io.*;
import java.util.*;

public class ListNode{
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }


import java.io.*;
import java.util.*;
import java.util.Stack;

    public class Solution {

        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();

        public void push(int node) {
            s1.push(node);
            if (s2.isEmpty() || s2.peek() > node){
                s2.push(node);
            }else s2.push(s2.peek());
        }

        public void pop() {
            s1.pop();
            s2.pop();
        }

        public int top() {
            return s1.peek();
        }

        public int min() {
            return s2.peek();
        }

import java.lang.reflect.Array;
import java.util.*;

        public class Test {

            public static List REMOVE(List<String> list){

                List<String> map = new ArrayList<>();
                for (int i = 0; i < list.size(); i++) {
                    if (!map.contains(list.get(i))){
                        map.add(list.get(i));//不存在才可以存进map中
                    }
                }
                return map;
            }
            public static void main1(String[] args) {
                List<String> list = new ArrayList<>();
                list.add("apple");
                list.add("banana");
                list.add("apple");
                list.add("orange");
                list.add("banana");
                list.add("grape");
                list.add("grape");
                System.out.println(REMOVE(list));


            }

            public static Map<String,Integer> cotain(List<String> list){

                Map<String,Integer> countMap = new HashMap<>();
                for ( String tmp: list) {
                    countMap.put(tmp,countMap.getOrDefault(tmp,0)+1);

                }
                return countMap;
            }

            public static void main2(String[] args) {
                List<String> list = new ArrayList<>();
                list.add("apple");
                list.add("banana");
                list.add("apple");
                list.add("orange");
                list.add("banana");
                list.add("grape");
                list.add("grape");
                System.out.println("水果出现的数量:" + cotain(list));
            }

            public static Map<String,List<String>> spilt(List<String> list){

                List<String> num = new ArrayList<>();
                List<String> str = new ArrayList<>();

                for (String s:list) {
                    if(s.matches("\\d+")){
                        num.add(s);
                    }else if(s.matches("[a-zA-Z]+")){
                        str.add(s);
                    }
                }
                Map<String , List<String>> result = new HashMap<>();
                result.put("数字列表" , num);
                result.put("字母列表" , str);
                return result;
            }

            public static void main(String[] args) {
                List<String > list = Arrays.asList("123","abc","456","def","789","ghi");
                System.out.println(spilt(list));



            }
            private static int partition(int[] array, int left, int right) {
                int i = left;
                int j = right;
                int pivot = array[left];
                while (i < j) {
                    while (i < j && array[j] >= pivot) {
                        j--;
                    }
                    while (i < j && array[i] <= pivot) {
                        i++;
                    }
                    swap(array, i, j);
                }
                swap(array, i, left);
                return i;
            }
            public static int gcd(int a,int b){ // 不需要判断a和b的大小
                while(b>0){
                    a%=b;b^=a;a^=b;b^=a;
//           while(b^=a^=b^=a%=b);
                }
                return a;
//        return (a % b == 0) ? b : gcd(b, a%b);
            }

            public static void cinInit(){
                cin.wordChars('a', 'z');
                cin.wordChars('A', 'Z');
                cin.wordChars(128 + 32, 255);
                cin.whitespaceChars(0, ' ');
                cin.commentChar('/');
                cin.quoteChar('"');
                cin.quoteChar('\'');
                cin.parseNumbers(); //可单独使用还原数字
            }
            public static int nextInt() throws Exception {
                cin.nextToken();
                return (int) cin.nval;
            }
            public static long nextLong() throws Exception {
                cin.nextToken();
                return (long) cin.nval;
            }
            public static double nextDouble() throws Exception {
                cin.nextToken();
                return cin.nval;
            }
            public static String nextString() throws Exception {
                cin.nextToken();
                return cin.sval;
            }
            public static void closeAll() throws Exception {
                cout.close();
                in.close();
                out.close();
            }

            public static void heapSort(int[] array) {
                int n = array.length;
                for (int i = n / 2 - 1; i >= 0; i--) {
                    heapify(array, n, i);
                }
                for (int i = n - 1; i >= 0; i--) {
                    int temp = array[0];
                    array[0] = array[i];
                    array[i] = temp;
                    heapify(array, i, 0);
                }
            }

            private static void heapify(int[] array, int n, int i) {
                int largest = i;
                int left = 2 * i + 1;
                int right = 2 * i + 2;
                if (left < n && array[left] > array[largest]) {
                    largest = left;
                }
                if (right < n && array[right] > array[largest]) {
                    largest = right;
                }
                if (largest != i) {
                    int swap = array[i];
                    array[i] = array[largest];
                    array[largest] = swap;
                    heapify(array, n, largest);
                }
            }
            public static void shellSort(int[] array) {
                int n = array.length;
                for (int gap = n / 2; gap > 0; gap /= 2) {
                    for (int i = gap; i < n; i++) {
                        int temp = array[i];
                        int j;
                        for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                            array[j] = array[j - gap];
                        }
                        array[j] = temp;
                    }
                }
            }





        }
import java.io.*;
import java.math.BigInteger;
import java.util.*;



        public class Main {
            public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
            public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
            public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
            public static Scanner sc = new Scanner(System.in);
            public static int monthes[]= {0,31,28,31,30,31,30,31,31,30,31,30,31};//一年中的12个月每月的天数
            public static int maxd = 1000+7;
            public static int INF = 0x3f3f3f3f;
            public static int mod = 998244353;

            public static int[][] a = new int[maxd][maxd];
            public static int[][] b = new int[maxd][maxd];


            public static void main(String[] args) throws Exception {

                int n = nextInt(); //行
                int m = nextInt(); //列
                for(int i=0;i<n;++i){
                    for(int j=0;j<m;++j){
                        a[i][j]=nextInt();
                    }
                }
                //旋转后还是为 n行 m列
                for(int i=0;i<n;++i){ //行
                    for(int j=0;j<m;++j){ //列
                        b[i][j]=a[n-1-i][m-1-j];
                    }
                }
                for(int i=0;i<n;++i){
                    for(int j=0;j<m;++j){
                        System.out.print(b[i][j]+" ");
                    }
                    System.out.println();
                }


                closeAll();
            }


            public static int gcd(int a,int b){ // 不需要判断a和b的大小
                while(b>0){
                    a%=b;b^=a;a^=b;b^=a;
//           while(b^=a^=b^=a%=b);
                }
                return a;
//        return (a % b == 0) ? b : gcd(b, a%b);
            }

            public static void cinInit(){
                cin.wordChars('a', 'z');
                cin.wordChars('A', 'Z');
                cin.wordChars(128 + 32, 255);
                cin.whitespaceChars(0, ' ');
                cin.commentChar('/');
                cin.quoteChar('"');
                cin.quoteChar('\'');
                cin.parseNumbers(); //可单独使用还原数字
            }
            public static int nextInt() throws Exception {
                cin.nextToken();
                return (int) cin.nval;
            }
            public static long nextLong() throws Exception {
                cin.nextToken();
                return (long) cin.nval;
            }
            public static double nextDouble() throws Exception {
                cin.nextToken();
                return cin.nval;
            }
            public static String nextString() throws Exception {
                cin.nextToken();
                return cin.sval;
            }
            public static void closeAll() throws Exception {
                cout.close();
                in.close();
                out.close();
            }
            public static void heapSort(int[] array) {
                int n = array.length;
                for (int i = n / 2 - 1; i >= 0; i--) {
                    heapify(array, n, i);
                }
                for (int i = n - 1; i >= 0; i--) {
                    int temp = array[0];
                    array[0] = array[i];
                    array[i] = temp;
                    heapify(array, i, 0);
                }
            }

            private static void heapify(int[] array, int n, int i) {
                int largest = i;
                int left = 2 * i + 1;
                int right = 2 * i + 2;
                if (left < n && array[left] > array[largest]) {
                    largest = left;
                }
                if (right < n && array[right] > array[largest]) {
                    largest = right;
                }
                if (largest != i) {
                    int swap = array[i];
                    array[i] = array[largest];
                    array[largest] = swap;
                    heapify(array, n, largest);
                }
            }
            public int threeSumClosest(int[] nums, int target) {
                Arrays.sort(nums);
                int n = nums.length;
                int best = 10000000;

                // 枚举 a
                for (int i = 0; i < n; ++i) {
                    // 保证和上一次枚举的元素不相等
                    if (i > 0 && nums[i] == nums[i - 1]) {
                        continue;
                    }
                    // 使用双指针枚举 b 和 c
                    int j = i + 1, k = n - 1;
                    while (j < k) {
                        int sum = nums[i] + nums[j] + nums[k];
                        // 如果和为 target 直接返回答案
                        if (sum == target) {
                            return target;
                        }
                        // 根据差值的绝对值来更新答案
                        if (Math.abs(sum - target) < Math.abs(best - target)) {
                            best = sum;
                        }
                        if (sum > target) {
                            // 如果和大于 target，移动 c 对应的指针
                            int k0 = k - 1;
                            // 移动到下一个不相等的元素
                            while (j < k0 && nums[k0] == nums[k]) {
                                --k0;
                            }
                            k = k0;
                        } else {
                            // 如果和小于 target，移动 b 对应的指针
                            int j0 = j + 1;
                            // 移动到下一个不相等的元素
                            while (j0 < k && nums[j0] == nums[j]) {
                                ++j0;
                            }
                            j = j0;
                        }
                    }
                }
                return best;
            }
            public static Map<String,List<String>> spilt(List<String> list){

                List<String> num = new ArrayList<>();
                List<String> str = new ArrayList<>();

                for (String s:list) {
                    if(s.matches("\\d+")){
                        num.add(s);
                    }else if(s.matches("[a-zA-Z]+")){
                        str.add(s);
                    }
                }
                Map<String , List<String>> result = new HashMap<>();
                result.put("数字列表" , num);
                result.put("字母列表" , str);
                return result;
            }

            public static void main(String[] args) {
                List<String > list = Arrays.asList("123","abc","456","def","789","ghi");
                System.out.println(spilt(list));



            }
            private static int partition(int[] array, int left, int right) {
                int i = left;
                int j = right;
                int pivot = array[left];
                while (i < j) {
                    while (i < j && array[j] >= pivot) {
                        j--;
                    }
                    while (i < j && array[i] <= pivot) {
                        i++;
                    }
                    swap(array, i, j);
                }
                swap(array, i, left);
                return i;
            }
            public static int gcd(int a,int b){ // 不需要判断a和b的大小
                while(b>0){
                    a%=b;b^=a;a^=b;b^=a;
//           while(b^=a^=b^=a%=b);
                }
                return a;
//        return (a % b == 0) ? b : gcd(b, a%b);
            }

            public static void cinInit(){
                cin.wordChars('a', 'z');
                cin.wordChars('A', 'Z');
                cin.wordChars(128 + 32, 255);
                cin.whitespaceChars(0, ' ');
                cin.commentChar('/');
                cin.quoteChar('"');
                cin.quoteChar('\'');
                cin.parseNumbers(); //可单独使用还原数字
            }

            public int threeSumClosest(int[] nums, int target) {
                Arrays.sort(nums);
                int n = nums.length;
                int best = 10000000;

                // 枚举 a
                for (int i = 0; i < n; ++i) {
                    // 保证和上一次枚举的元素不相等
                    if (i > 0 && nums[i] == nums[i - 1]) {
                        continue;
                    }
                    // 使用双指针枚举 b 和 c
                    int j = i + 1, k = n - 1;
                    while (j < k) {
                        int sum = nums[i] + nums[j] + nums[k];
                        // 如果和为 target 直接返回答案
                        if (sum == target) {
                            return target;
                        }
                        // 根据差值的绝对值来更新答案
                        if (Math.abs(sum - target) < Math.abs(best - target)) {
                            best = sum;
                        }
                        if (sum > target) {
                            // 如果和大于 target，移动 c 对应的指针
                            int k0 = k - 1;
                            // 移动到下一个不相等的元素
                            while (j < k0 && nums[k0] == nums[k]) {
                                --k0;
                            }
                            k = k0;
                        } else {
                            // 如果和小于 target，移动 b 对应的指针
                            int j0 = j + 1;
                            // 移动到下一个不相等的元素
                            while (j0 < k && nums[j0] == nums[j]) {
                                ++j0;
                            }
                            j = j0;
                        }
                    }
                }
                return best;
            }
            public static void heapSort(int[] array) {
                int n = array.length;
                for (int i = n / 2 - 1; i >= 0; i--) {
                    heapify(array, n, i);
                }
                for (int i = n - 1; i >= 0; i--) {
                    int temp = array[0];
                    array[0] = array[i];
                    array[i] = temp;
                    heapify(array, i, 0);
                }
            }
            public static List REMOVE(List<String> list){

                List<String> map = new ArrayList<>();
                for (int i = 0; i < list.size(); i++) {
                    if (!map.contains(list.get(i))){
                        map.add(list.get(i));//不存在才可以存进map中
                    }
                }
                return map;
            }
            public static void main1(String[] args) {
                List<String> list = new ArrayList<>();
                list.add("apple");
                list.add("banana");
                list.add("apple");
                list.add("orange");
                list.add("banana");
                list.add("grape");
                list.add("grape");
                System.out.println(REMOVE(list));


            }

            public static Map<String,Integer> cotain(List<String> list){

                Map<String,Integer> countMap = new HashMap<>();
                for ( String tmp: list) {
                    countMap.put(tmp,countMap.getOrDefault(tmp,0)+1);

                }
                return countMap;
            }

            public static void main2(String[] args) {
                List<String> list = new ArrayList<>();
                list.add("apple");
                list.add("banana");
                list.add("apple");
                list.add("orange");
                list.add("banana");
                list.add("grape");
                list.add("grape");
                System.out.println("水果出现的数量:" + cotain(list));
            }
            public static void heapSort(int[] array) {
                int n = array.length;
                for (int i = n / 2 - 1; i >= 0; i--) {
                    heapify(array, n, i);
                }
                for (int i = n - 1; i >= 0; i--) {
                    int temp = array[0];
                    array[0] = array[i];
                    array[i] = temp;
                    heapify(array, i, 0);
                }
            }

            private static void heapify(int[] array, int n, int i) {
                int largest = i;
                int left = 2 * i + 1;
                int right = 2 * i + 2;
                if (left < n && array[left] > array[largest]) {
                    largest = left;
                }
                if (right < n && array[right] > array[largest]) {
                    largest = right;
                }
                if (largest != i) {
                    int swap = array[i];
                    array[i] = array[largest];
                    array[largest] = swap;
                    heapify(array, n, largest);
                }
            }

            public class ListNode{
                int val;
                Solution.Main.ListNode next;
                ListNode() {}
                ListNode(int val) { this.val = val; }
                ListNode(int val, Solution.Main.ListNode next) { this.val = val; this.next = next; }




                //    移除链表元素
//    给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
//
//    输入：head = [1,2,6,3,4,5,6], val = 6
//    输出：[1,2,3,4,5]
                class Solution {


                    public Solution.Main.ListNode removeElements(Solution.Main.ListNode head, int val) {


                        if (head == null) {
                            return null;
                        }

                        Solution.Main.ListNode prev = head;
                        Solution.Main.ListNode tmep = prev;
                        Solution.Main.ListNode cur = head.next;

                        while (cur != null) {
                            if (cur.val == val) {
                                tmep.next = cur.next;
                                cur = cur.next;
                            } else {
                                tmep = cur;
                                cur = cur.next;
                            }
                        }

                        if (prev.val == val) {
                            prev = prev.next;
                        }
                        return prev;
                    }

                }
            }



        }


    }
import java.io.*;
        import java.util.*;

    // 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
//
//         返回这三个数的和。
//
//         假定每组输入只存在恰好一个解。
    class Soluion {
        public int threeSumClosest(int[] nums, int target) {
            Arrays.sort(nums);
            int n = nums.length;
            int best = 10000000;

            // 枚举 a
            for (int i = 0; i < n; ++i) {
                // 保证和上一次枚举的元素不相等
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                // 使用双指针枚举 b 和 c
                int j = i + 1, k = n - 1;
                while (j < k) {
                    int sum = nums[i] + nums[j] + nums[k];
                    // 如果和为 target 直接返回答案
                    if (sum == target) {
                        return target;
                    }
                    // 根据差值的绝对值来更新答案
                    if (Math.abs(sum - target) < Math.abs(best - target)) {
                        best = sum;
                    }
                    if (sum > target) {
                        // 如果和大于 target，移动 c 对应的指针
                        int k0 = k - 1;
                        // 移动到下一个不相等的元素
                        while (j < k0 && nums[k0] == nums[k]) {
                            --k0;
                        }
                        k = k0;
                    } else {
                        // 如果和小于 target，移动 b 对应的指针
                        int j0 = j + 1;
                        // 移动到下一个不相等的元素
                        while (j0 < k && nums[j0] == nums[j]) {
                            ++j0;
                        }
                        j = j0;
                    }
                }
            }
            return best;
        }
        public static void heapSort(int[] array) {
            int n = array.length;
            for (int i = n / 2 - 1; i >= 0; i--) {
                heapify(array, n, i);
            }
            for (int i = n - 1; i >= 0; i--) {
                int temp = array[0];
                array[0] = array[i];
                array[i] = temp;
                heapify(array, i, 0);
            }
        }

        private static void heapify(int[] array, int n, int i) {
            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            if (left < n && array[left] > array[largest]) {
                largest = left;
            }
            if (right < n && array[right] > array[largest]) {
                largest = right;
            }
            if (largest != i) {
                int swap = array[i];
                array[i] = array[largest];
                array[largest] = swap;
                heapify(array, n, largest);
            }
        }
        public static void shellSort(int[] array) {
            int n = array.length;
            for (int gap = n / 2; gap > 0; gap /= 2) {
                for (int i = gap; i < n; i++) {
                    int temp = array[i];
                    int j;
                    for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                        array[j] = array[j - gap];
                    }
                    array[j] = temp;
                }
            }
        }


        public class ListNode{
            int val;
            ListNode next;
            ListNode() {}
            ListNode(int val) { this.val = val; }
            ListNode(int val, ListNode next) { this.val = val; this.next = next; }




            //    移除链表元素
//    给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
//
//    输入：head = [1,2,6,3,4,5,6], val = 6
//    输出：[1,2,3,4,5]
            class Solution {


                public ListNode removeElements(ListNode head, int val) {


                    if (head == null) {
                        return null;
                    }

                    ListNode prev = head;
                    ListNode tmep = prev;
                    ListNode cur = head.next;

                    while (cur != null) {
                        if (cur.val == val) {
                            tmep.next = cur.next;
                            cur = cur.next;
                        } else {
                            tmep = cur;
                            cur = cur.next;
                        }
                    }

                    if (prev.val == val) {
                        prev = prev.next;
                    }
                    return prev;
                }

            }
        }


        public class ListNode{
            int val;
            ListNode next;
            ListNode() {}
            ListNode(int val) { this.val = val; }
            ListNode(int val, ListNode next) { this.val = val; this.next = next; }




            //    移除链表元素
//    给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
//
//    输入：head = [1,2,6,3,4,5,6], val = 6
//    输出：[1,2,3,4,5]
            class Solution {


                public ListNode removeElements(ListNode head, int val) {


                    if (head == null) {
                        return null;
                    }

                    ListNode prev = head;
                    ListNode tmep = prev;
                    ListNode cur = head.next;

                    while (cur != null) {
                        if (cur.val == val) {
                            tmep.next = cur.next;
                            cur = cur.next;
                        } else {
                            tmep = cur;
                            cur = cur.next;
                        }
                    }

                    if (prev.val == val) {
                        prev = prev.next;
                    }
                    return prev;
                }

            }
        }


import java.io.*;
import java.math.BigInteger;
import java.util.*;



        public class Main {
            public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
            public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
            public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
            public static Scanner sc = new Scanner(System.in);
            public static int monthes[]= {0,31,28,31,30,31,30,31,31,30,31,30,31};//一年中的12个月每月的天数
            public static int maxd = 1000+7;
            public static int INF = 0x3f3f3f3f;
            public static int mod = 998244353;

            public static int[][] a = new int[maxd][maxd];
            public static int[][] b = new int[maxd][maxd];


            public static void main(String[] args) throws Exception {

                int n = nextInt(); //行
                int m = nextInt(); //列
                for(int i=0;i<n;++i){
                    for(int j=0;j<m;++j){
                        a[i][j]=nextInt();
                    }
                }
                //旋转后还是为 n行 m列
                for(int i=0;i<n;++i){ //行
                    for(int j=0;j<m;++j){ //列
                        b[i][j]=a[n-1-i][m-1-j];
                    }
                }
                for(int i=0;i<n;++i){
                    for(int j=0;j<m;++j){
                        System.out.print(b[i][j]+" ");
                    }
                    System.out.println();
                }


                closeAll();
            }


            public static int gcd(int a,int b){ // 不需要判断a和b的大小
                while(b>0){
                    a%=b;b^=a;a^=b;b^=a;
//           while(b^=a^=b^=a%=b);
                }
                return a;
//        return (a % b == 0) ? b : gcd(b, a%b);
            }

            public static void cinInit(){
                cin.wordChars('a', 'z');
                cin.wordChars('A', 'Z');
                cin.wordChars(128 + 32, 255);
                cin.whitespaceChars(0, ' ');
                cin.commentChar('/');
                cin.quoteChar('"');
                cin.quoteChar('\'');
                cin.parseNumbers(); //可单独使用还原数字
            }
            public static int nextInt() throws Exception {
                cin.nextToken();
                return (int) cin.nval;
            }
            public static long nextLong() throws Exception {
                cin.nextToken();
                return (long) cin.nval;
            }
            public static double nextDouble() throws Exception {
                cin.nextToken();
                return cin.nval;
            }
            public static String nextString() throws Exception {
                cin.nextToken();
                return cin.sval;
            }
            public static void closeAll() throws Exception {
                cout.close();
                in.close();
                out.close();
            }
            public static void heapSort(int[] array) {
                int n = array.length;
                for (int i = n / 2 - 1; i >= 0; i--) {
                    heapify(array, n, i);
                }
                for (int i = n - 1; i >= 0; i--) {
                    int temp = array[0];
                    array[0] = array[i];
                    array[i] = temp;
                    heapify(array, i, 0);
                }
            }

            private static void heapify(int[] array, int n, int i) {
                int largest = i;
                int left = 2 * i + 1;
                int right = 2 * i + 2;
                if (left < n && array[left] > array[largest]) {
                    largest = left;
                }
                if (right < n && array[right] > array[largest]) {
                    largest = right;
                }
                if (largest != i) {
                    int swap = array[i];
                    array[i] = array[largest];
                    array[largest] = swap;
                    heapify(array, n, largest);
                }
            }
            public int threeSumClosest(int[] nums, int target) {
                Arrays.sort(nums);
                int n = nums.length;
                int best = 10000000;

                // 枚举 a
                for (int i = 0; i < n; ++i) {
                    // 保证和上一次枚举的元素不相等
                    if (i > 0 && nums[i] == nums[i - 1]) {
                        continue;
                    }
                    // 使用双指针枚举 b 和 c
                    int j = i + 1, k = n - 1;
                    while (j < k) {
                        int sum = nums[i] + nums[j] + nums[k];
                        // 如果和为 target 直接返回答案
                        if (sum == target) {
                            return target;
                        }
                        // 根据差值的绝对值来更新答案
                        if (Math.abs(sum - target) < Math.abs(best - target)) {
                            best = sum;
                        }
                        if (sum > target) {
                            // 如果和大于 target，移动 c 对应的指针
                            int k0 = k - 1;
                            // 移动到下一个不相等的元素
                            while (j < k0 && nums[k0] == nums[k]) {
                                --k0;
                            }
                            k = k0;
                        } else {
                            // 如果和小于 target，移动 b 对应的指针
                            int j0 = j + 1;
                            // 移动到下一个不相等的元素
                            while (j0 < k && nums[j0] == nums[j]) {
                                ++j0;
                            }
                            j = j0;
                        }
                    }
                }
                return best;
            }
            public static Map<String, List<String>> spilt(List<String> list){

                List<String> num = new ArrayList<>();
                List<String> str = new ArrayList<>();

                for (String s:list) {
                    if(s.matches("\\d+")){
                        num.add(s);
                    }else if(s.matches("[a-zA-Z]+")){
                        str.add(s);
                    }
                }
                Map<String , List<String>> result = new HashMap<>();
                result.put("数字列表" , num);
                result.put("字母列表" , str);
                return result;
            }

            public static void main(String[] args) {
                List<String > list = Arrays.asList("123","abc","456","def","789","ghi");
                System.out.println(spilt(list));



            }
            private static int partition(int[] array, int left, int right) {
                int i = left;
                int j = right;
                int pivot = array[left];
                while (i < j) {
                    while (i < j && array[j] >= pivot) {
                        j--;
                    }
                    while (i < j && array[i] <= pivot) {
                        i++;
                    }
                    swap(array, i, j);
                }
                swap(array, i, left);
                return i;
            }
            public static int gcd(int a,int b){ // 不需要判断a和b的大小
                while(b>0){
                    a%=b;b^=a;a^=b;b^=a;
//           while(b^=a^=b^=a%=b);
                }
                return a;
//        return (a % b == 0) ? b : gcd(b, a%b);
            }

            public static void cinInit(){
                cin.wordChars('a', 'z');
                cin.wordChars('A', 'Z');
                cin.wordChars(128 + 32, 255);
                cin.whitespaceChars(0, ' ');
                cin.commentChar('/');
                cin.quoteChar('"');
                cin.quoteChar('\'');
                cin.parseNumbers(); //可单独使用还原数字
            }

            public int threeSumClosest(int[] nums, int target) {
                Arrays.sort(nums);
                int n = nums.length;
                int best = 10000000;

                // 枚举 a
                for (int i = 0; i < n; ++i) {
                    // 保证和上一次枚举的元素不相等
                    if (i > 0 && nums[i] == nums[i - 1]) {
                        continue;
                    }
                    // 使用双指针枚举 b 和 c
                    int j = i + 1, k = n - 1;
                    while (j < k) {
                        int sum = nums[i] + nums[j] + nums[k];
                        // 如果和为 target 直接返回答案
                        if (sum == target) {
                            return target;
                        }
                        // 根据差值的绝对值来更新答案
                        if (Math.abs(sum - target) < Math.abs(best - target)) {
                            best = sum;
                        }
                        if (sum > target) {
                            // 如果和大于 target，移动 c 对应的指针
                            int k0 = k - 1;
                            // 移动到下一个不相等的元素
                            while (j < k0 && nums[k0] == nums[k]) {
                                --k0;
                            }
                            k = k0;
                        } else {
                            // 如果和小于 target，移动 b 对应的指针
                            int j0 = j + 1;
                            // 移动到下一个不相等的元素
                            while (j0 < k && nums[j0] == nums[j]) {
                                ++j0;
                            }
                            j = j0;
                        }
                    }
                }
                return best;
            }
            public static void heapSort(int[] array) {
                int n = array.length;
                for (int i = n / 2 - 1; i >= 0; i--) {
                    heapify(array, n, i);
                }
                for (int i = n - 1; i >= 0; i--) {
                    int temp = array[0];
                    array[0] = array[i];
                    array[i] = temp;
                    heapify(array, i, 0);
                }
            }
            public static List REMOVE(List<String> list){

                List<String> map = new ArrayList<>();
                for (int i = 0; i < list.size(); i++) {
                    if (!map.contains(list.get(i))){
                        map.add(list.get(i));//不存在才可以存进map中
                    }
                }
                return map;
            }
            public static void main1(String[] args) {
                List<String> list = new ArrayList<>();
                list.add("apple");
                list.add("banana");
                list.add("apple");
                list.add("orange");
                list.add("banana");
                list.add("grape");
                list.add("grape");
                System.out.println(REMOVE(list));


            }

            public static Map<String,Integer> cotain(List<String> list){

                Map<String,Integer> countMap = new HashMap<>();
                for ( String tmp: list) {
                    countMap.put(tmp,countMap.getOrDefault(tmp,0)+1);

                }
                return countMap;
            }

            public static void main2(String[] args) {
                List<String> list = new ArrayList<>();
                list.add("apple");
                list.add("banana");
                list.add("apple");
                list.add("orange");
                list.add("banana");
                list.add("grape");
                list.add("grape");
                System.out.println("水果出现的数量:" + cotain(list));
            }
            public static void heapSort(int[] array) {
                int n = array.length;
                for (int i = n / 2 - 1; i >= 0; i--) {
                    heapify(array, n, i);
                }
                for (int i = n - 1; i >= 0; i--) {
                    int temp = array[0];
                    array[0] = array[i];
                    array[i] = temp;
                    heapify(array, i, 0);
                }
            }

            private static void heapify(int[] array, int n, int i) {
                int largest = i;
                int left = 2 * i + 1;
                int right = 2 * i + 2;
                if (left < n && array[left] > array[largest]) {
                    largest = left;
                }
                if (right < n && array[right] > array[largest]) {
                    largest = right;
                }
                if (largest != i) {
                    int swap = array[i];
                    array[i] = array[largest];
                    array[largest] = swap;
                    heapify(array, n, largest);
                }
            }

            public class ListNode{
                int val;
                ListNode next;
                ListNode() {}
                ListNode(int val) { this.val = val; }
                ListNode(int val, ListNode next) { this.val = val; this.next = next; }




                //    移除链表元素
//    给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
//
//    输入：head = [1,2,6,3,4,5,6], val = 6
//    输出：[1,2,3,4,5]
                class Solution {


                    public ListNode removeElements(ListNode head, int val) {


                        if (head == null) {
                            return null;
                        }

                        ListNode prev = head;
                        ListNode tmep = prev;
                        ListNode cur = head.next;

                        while (cur != null) {
                            if (cur.val == val) {
                                tmep.next = cur.next;
                                cur = cur.next;
                            } else {
                                tmep = cur;
                                cur = cur.next;
                            }
                        }

                        if (prev.val == val) {
                            prev = prev.next;
                        }
                        return prev;
                    }

                }
            }



        }

import java.util.Arrays;
import java.util.List;
import java.util.Stack;

        public class SORT {
            //直接插入排序
            /*
             * 时间复杂度：
             *      最好情况：数据有序的情况下：O(N)
             *      最坏情况：数据逆序的时候-》O(N^2)
             * 空间复杂度：O(1)
             * 稳定性：稳定的
             *     一个本身就不稳定的排序，是不可能变成一个稳定的排序的
             *     但是一个本身就稳定的排序，是可以实现为不稳定的排序的
             * 特点：数据越有序，直接插入排序越快
             * 特点：数据越趋于有序，直接插入排序越快*/
            public static void insertSort(int[] array){
                for(int i = 1;i < array.length;i++){
                    int tmp = array[i];
                    int j = i -1;
                    for (;j > 0;j--){
                        //j>=0 可以决定这个排序的稳定性
                        if(array[j] > tmp){
                            array[j+1] = array[j];
                        }else {
                            //array[j+1] = tmp;
                            break;
                        }
                    }
                    array[j+1] = tmp;
                }
            }
            //希尔排序
            public  static void shellSort(int[] array){
                int gap = array.length;
                while (gap > 1 ){
                    gap /= 2;
                    shell(array,gap);
                }
            }
            public  static  void shell(int[] array, int gap){
                for(int i = gap;i < array.length;i++){
                    int tmp = array[i];
                    int j = i -gap;
                    for (;j >= 0;j -= gap){
                        //j>=0 可以决定这个排序的稳定性
                        if(array[j] > tmp){
                            array[j+gap] = array[j];
                        }else {
                            //array[j+1] = tmp;
                            break;
                        }
                    }
                    array[j+gap] = tmp;
                }
            }
            public static void main(String[] args) {
                int[] arr = {5, 2, 9, 1, 5, 6};
                //shellSort(arr);
                selectSort(arr);
                System.out.println(Arrays.toString(arr)); // 输出: [1, 2, 5, 5, 6, 9]
            }
            /*选择排序
             选择排序：
               时间复杂度：O(N^2)
                 空间复杂度：O(1)
               稳定性：不稳定*/
            public static void selectSort(int[] array){
                for (int i = 0; i < array.length;i++){
                    int minIndex = i;
                    int j = i + 1;
                    for (;j  < array.length;j++){
                        if(array[j] < array[minIndex]){
                            minIndex = j;
                        }
                    }
                    swap(array,i,minIndex);
                }
            }
            public static void swap(int[] array,int i , int j){
                int tmp = array[j];
                array[j] = array[i];
                array[i] = tmp;
            }

            public static  void selectSort2(int[] array){
                int left = 0;
                int right = array.length-1;
                while (left < right){
                    int minIndex = left;
                    int maxIndex = left;
                    for (int i = left+1;i <= right;i++){
                        if (array[i] < array[minIndex]){
                            minIndex = i;
                        }
                        if (array[i] > array[maxIndex]){
                            maxIndex = i;
                        }
                    }
                    swap(array,minIndex,left);
                    if (minIndex == left){
                        maxIndex = minIndex;
                    }
                    swap(array,maxIndex,right);
                    left++;
                    right--;
                }
            }
            //堆排序
            public  static void heapSoet(int[] array){
                createHeap(array);
                int end = array.length - 1;
                while (end > 0){
                    swap(array,0,end);
                    siftDown(array,0,end);
                    end--;
                }



            }
            //创建大根堆
            public  static  void createHeap(int[] array){
                for (int parent = (array.length-1-1)/2;parent >=0;parent--) {
                    siftDown(array, parent, array.length);
                }
            }
            public static void siftDown(int[] array,int parent,int len){
                int child = (2*parent) + 1;
                while (child  < len ){
                    if (child + 1 < len && array[child]  <array[child+1]){
                        child = child +1;
                    }
                    if (array[child] > array[parent]){
                        swap(array, child, parent);
                        parent = child;
                        child = (2*parent) + 1;
                    }else{
                        break;
                    }
                }
            }

            //快速排序
            public static void quickSort(int[] array){
                quick(array,0,array.length-1);
            }
            public static void quick(int[] array,int start,int end){
                if (start >= end){
                    return;
                }
                if (end -start+1 <= 15){
                    insertSort2(array,start,end);
                    return;
                }

                //1. 三数取中  index是中间大的数字 的 下标
                int index = middleNum(array,start,end);
                int pivot = partitionHoare(array,start,end);
                quick(array,start,pivot-1);
                quick(array,pivot+1,end);

            }
            public static void insertSort2(int[] array,int start,int end){
                for(int i = start+1;i <= end;i++){
                    int tmp = array[i];
                    int j = i -1;
                    for (;j >= start;j--){
                        //j>=0 可以决定这个排序的稳定性
                        if(array[j] > tmp){
                            array[j+1] = array[j];
                        }else {
                            //array[j+1] = tmp;
                            break;
                        }
                    }
                    array[j+1] = tmp;
                }
            }
            private static int middleNum(int[]array,int left,int right){
                int mid = left + ((left+right) >> 1);
                if (array[left] < array[right]){
                    if (array[mid] < array[left]){
                        return left;
                    }else if (array[mid] > array[right]){
                        return right;
                    } else  {
                        return mid;
                    }
                }else if (array[mid] > array[left]){
                    return left;
                }else if(array[mid] < array[right]){
                    return right;
                }else {
                    return mid;
                }
            }

            public static int partitionHoare(int[] array,int left,int right){
                int tmp = array[left];
                int i = left;
                while (left < right){
                    while (left < right && array[right] >= tmp){
                        right--;
                    }
                    while (left < right && array[left] <= tmp){
                        left++;
                    }
                    swap(array,left,right);
                }
                swap(array,i,left);
                return left;
            }
            //挖坑法
            public static int partition(int[] array,int left,int right){
                int tmp = array[left];
                while(left < right){
                    while (left < right && array[right] >= tmp){
                        right--;
                    }
                    if(left >= right) {
                        break;
                    }
                    array[left] = array[right];
                    while (left < right && array[left] <= tmp){
                        left++;
                    }
                    if(left >= right) {
                        break;
                    }
                    array[right] = array[left];
                }
                array[left] = tmp;
                return left;
            }


            public static void quickSortNor(int[] array){
                Stack<Integer> stack = new Stack<>();
                int left = 0;
                int right = array.length-1;
                int pivot = partitionHoare(array,left,right);

                if (pivot-1 > left){
                    stack.push(left);
                    stack.push(pivot-1);
                }
                if (pivot+1 < right){
                    stack.push(pivot+1);
                    stack.push(right);
                }
                while(!stack.isEmpty()){
                    right = stack.pop();
                    left = stack.pop();
                    if (pivot-1 > left){
                        stack.push(left);
                        stack.push(pivot-1);
                    }
                    if (pivot+1 < right){
                        stack.push(pivot+1);
                        stack.push(right);
                    }
                }
            }
            //归并排序
            public static void mergesort(int[] array){
                mergeFunc(array,0,array.length-1);
            }
            public static void mergeFunc(int[] array,int left,int right){
                if(left >= right){
                    return;
                }
                int mid = left + ((left + right) >> 1);
                mergeFunc(array, left, mid);
                mergeFunc(array, mid+1, right);
                merge(array,left,mid,right);
            }
            public static void merge(int[] array,int left,int mid,int right){
                int s1 = left;
                int e1 = mid;
                int s2 = mid+1;
                int e2 = right;
                int[] tmpArr = new int[right-left+1];
                int k = 0;
                while (s1 <= e1 && s2 <= e2){
                    if (array[s1] <= array[s2]){
                        tmpArr[k++] = array[s1++];
                    }else {
                        tmpArr[k++] = array[s2++];
                    }
                }
                while (s1 <= e1){
                    tmpArr[k++] = array[s1++];
                }
                while (s2<= e2){
                    tmpArr[k++] = array[s2++];
                }
                for (int i = 0;i < k;i++){
                    array[i+left] = tmpArr[i];
                }
            }


            public static void bubbleSort(int[] array){
                for (int i = 0;i<array.length-1;i++){
                    boolean flg = false;
                    for (int j = 0;j<array.length-1-i;j++){
                        if (array[j] > array[j+1]){
                            swap(array,j,j+1);
                            flg = true;
                        }
                    }
                    if (flg == false){
                        return;
                    }
                }

        import java.util.*;
                public class Solution {
                    public int findPeakElement (int[] nums) {
                        int left = 0;
                        int right = nums.length - 1;
                        //二分法
                        while(left < right){
                            int mid = (left + right) / 2;
                            //右边是往下，不一定有坡峰
                            if(nums[mid] > nums[mid + 1])
                                right = mid;
                                //右边是往上，一定能找到波峰
                            else
                                left = mid + 1;
                        }
                        //其中一个波峰
                        return right;
                    }
                }

                public class MyRunnable implements Runnable {
                    public void run() {
                        // 在这里编写线程执行的代码
                        System.out.println("This is a thread implementing Runnable interface");
                    }
                }

                MyRunnable myRunnable = new MyRunnable();
                Thread thread = new Thread(myRunnable);
                thread.start();

                public class MyRunnable implements Runnable {
                    public void run() {
                        // 在这里编写线程执行的代码
                        System.out.println("This is a thread implementing Runnable interface");
                    }
                }

                MyRunnable myRunnable = new MyRunnable();
                Thread thread = new Thread(myRunnable);
                thread.start();

            }



            public static void merge(int[] array,int left,int mid,int right){
                int s1 = left;
                int e1 = mid;
                int s2 = mid+1;
                int e2 = right;
                int[] tmpArr = new int[right-left+1];
                int k = 0;
                while (s1 <= e1 && s2 <= e2){
                    if (array[s1] <= array[s2]){
                        tmpArr[k++] = array[s1++];
                    }else {
                        tmpArr[k++] = array[s2++];
                    }
                }
                while (s1 <= e1){
                    tmpArr[k++] = array[s1++];
                }
                while (s2<= e2){
                    tmpArr[k++] = array[s2++];
                }
                for (int i = 0;i < k;i++){
                    array[i+left] = tmpArr[i];
                }
            }


            public static void bubbleSort(int[] array){
                for (int i = 0;i<array.length-1;i++){
                    boolean flg = false;
                    for (int j = 0;j<array.length-1-i;j++){
                        if (array[j] > array[j+1]){
                            swap(array,j,j+1);
                            flg = true;
                        }
                    }
                    if (flg == false){
                        return;
                    }
                }




import java.util.Arrays;
// 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
//
//         返回这三个数的和。
//
//         假定每组输入只存在恰好一个解。
                class Soluion {
                    public int threeSumClosest(int[] nums, int target) {
                        Arrays.sort(nums);
                        int n = nums.length;
                        int best = 10000000;

                        // 枚举 a
                        for (int i = 0; i < n; ++i) {
                            // 保证和上一次枚举的元素不相等
                            if (i > 0 && nums[i] == nums[i - 1]) {
                                continue;
                            }
                            // 使用双指针枚举 b 和 c
                            int j = i + 1, k = n - 1;
                            while (j < k) {
                                int sum = nums[i] + nums[j] + nums[k];
                                // 如果和为 target 直接返回答案
                                if (sum == target) {
                                    return target;
                                }
                                // 根据差值的绝对值来更新答案
                                if (Math.abs(sum - target) < Math.abs(best - target)) {
                                    best = sum;
                                }
                                if (sum > target) {
                                    // 如果和大于 target，移动 c 对应的指针
                                    int k0 = k - 1;
                                    // 移动到下一个不相等的元素
                                    while (j < k0 && nums[k0] == nums[k]) {
                                        --k0;
                                    }
                                    k = k0;
                                } else {
                                    // 如果和小于 target，移动 b 对应的指针
                                    int j0 = j + 1;
                                    // 移动到下一个不相等的元素
                                    while (j0 < k && nums[j0] == nums[j]) {
                                        ++j0;
                                    }
                                    j = j0;
                                }
                            }
                        }
                        return best;
                    }
                    public static void heapSort(int[] array) {
                        int n = array.length;
                        for (int i = n / 2 - 1; i >= 0; i--) {
                            heapify(array, n, i);
                        }
                        for (int i = n - 1; i >= 0; i--) {
                            int temp = array[0];
                            array[0] = array[i];
                            array[i] = temp;
                            heapify(array, i, 0);
                        }
                    }

                    private static void heapify(int[] array, int n, int i) {
                        int largest = i;
                        int left = 2 * i + 1;
                        int right = 2 * i + 2;
                        if (left < n && array[left] > array[largest]) {
                            largest = left;
                        }
                        if (right < n && array[right] > array[largest]) {
                            largest = right;
                        }
                        if (largest != i) {
                            int swap = array[i];
                            array[i] = array[largest];
                            array[largest] = swap;
                            heapify(array, n, largest);
                        }
                    }
                    public static void shellSort(int[] array) {
                        int n = array.length;
                        for (int gap = n / 2; gap > 0; gap /= 2) {
                            for (int i = gap; i < n; i++) {
                                int temp = array[i];
                                int j;
                                for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                                    array[j] = array[j - gap];
                                }
                                array[j] = temp;
                            }
                        }
                    }
                    public static void heapSort(int[] array) {
                        int n = array.length;
                        for (int i = n / 2 - 1; i >= 0; i--) {
                            heapify(array, n, i);
                        }
                        for (int i = n - 1; i >= 0; i--) {
                            int temp = array[0];
                            array[0] = array[i];
                            array[i] = temp;
                            heapify(array, i, 0);
                        }
                    }

                    private static void heapify(int[] array, int n, int i) {
                        int largest = i;
                        int left = 2 * i + 1;
                        int right = 2 * i + 2;
                        if (left < n && array[left] > array[largest]) {
                            largest = left;
                        }
                        if (right < n && array[right] > array[largest]) {
                            largest = right;
                        }
                        if (largest != i) {
                            int swap = array[i];
                            array[i] = array[largest];
                            array[largest] = swap;
                            heapify(array, n, largest);
                        }
                    }
                    public static void shellSort(int[] array) {
                        int n = array.length;
                        for (int gap = n / 2; gap > 0; gap /= 2) {
                            for (int i = gap; i < n; i++) {
                                int temp = array[i];
                                int j;
                                for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                                    array[j] = array[j - gap];
                                }
                                array[j] = temp;
                            }
                        }
                    }
                    public static void main(String[] args) {
                        List<String > list = Arrays.asList("123","abc","456","def","789","ghi");
                        System.out.println(spilt(list));



                    }
                    private static int partition(int[] array, int left, int right) {
                        int i = left;
                        int j = right;
                        int pivot = array[left];
                        while (i < j) {
                            while (i < j && array[j] >= pivot) {
                                j--;
                            }
                            while (i < j && array[i] <= pivot) {
                                i++;
                            }
                            swap(array, i, j);
                        }
                        swap(array, i, left);
                        return i;
                    }
                    public static int gcd(int a,int b){ // 不需要判断a和b的大小
                        while(b>0){
                            a%=b;b^=a;a^=b;b^=a;
//           while(b^=a^=b^=a%=b);
                        }
                        return a;
//        return (a % b == 0) ? b : gcd(b, a%b);
                    }

                    public static void cinInit(){
                        cin.wordChars('a', 'z');
                        cin.wordChars('A', 'Z');
                        cin.wordChars(128 + 32, 255);
                        cin.whitespaceChars(0, ' ');
                        cin.commentChar('/');
                        cin.quoteChar('"');
                        cin.quoteChar('\'');
                        cin.parseNumbers(); //可单独使用还原数字
                    }
                    public static int nextInt() throws Exception {
                        cin.nextToken();
                        return (int) cin.nval;
                    }
                    public static long nextLong() throws Exception {
                        cin.nextToken();
                        return (long) cin.nval;
                    }
                    public static double nextDouble() throws Exception {
                        cin.nextToken();
                        return cin.nval;
                    }
                    public static String nextString() throws Exception {
                        cin.nextToken();
                        return cin.sval;
                    }
                    public static void closeAll() throws Exception {
                        cout.close();
                        in.close();
                        out.close();
                    }











                    // 枚举 a
        for (int i = 0; i < n; ++i) {
                        // 保证和上一次枚举的元素不相等
                        if (i > 0 && nums[i] == nums[i - 1]) {
                            continue;
                        }
                        // 使用双指针枚举 b 和 c
                        int j = i + 1, k = n - 1;
                        while (j < k) {
                            int sum = nums[i] + nums[j] + nums[k];
                            // 如果和为 target 直接返回答案
                            if (sum == target) {
                                return target;
                            }
                            // 根据差值的绝对值来更新答案
                            if (Math.abs(sum - target) < Math.abs(best - target)) {
                                best = sum;
                            }
                            if (sum > target) {
                                // 如果和大于 target，移动 c 对应的指针
                                int k0 = k - 1;
                                // 移动到下一个不相等的元素
                                while (j < k0 && nums[k0] == nums[k]) {
                                    --k0;
                                }
                                k = k0;
                            } else {
                                // 如果和小于 target，移动 b 对应的指针
                                int j0 = j + 1;
                                // 移动到下一个不相等的元素
                                while (j0 < k && nums[j0] == nums[j]) {
                                    ++j0;
                                }
                                j = j0;
                            }
                        }
                    }
        return best;
                }
            }

        }


        public static void heapSort(int[] array) {
            int n = array.length;
            for (int i = n / 2 - 1; i >= 0; i--) {
                heapify(array, n, i);
            }
            for (int i = n - 1; i >= 0; i--) {
                int temp = array[0];
                array[0] = array[i];
                array[i] = temp;
                heapify(array, i, 0);
            }
        }

        private static void heapify(int[] array, int n, int i) {
            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            if (left < n && array[left] > array[largest]) {
                largest = left;
            }
            if (right < n && array[right] > array[largest]) {
                largest = right;
            }
            if (largest != i) {
                int swap = array[i];
                array[i] = array[largest];
                array[largest] = swap;
                heapify(array, n, largest);
            }
        }
        public static void shellSort(int[] array) {
            int n = array.length;
            for (int gap = n / 2; gap > 0; gap /= 2) {
                for (int i = gap; i < n; i++) {
                    int temp = array[i];
                    int j;
                    for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                        array[j] = array[j - gap];
                    }
                    array[j] = temp;
                }
            }
        }
        // 枚举 a
        for (int i = 0; i < n; ++i) {
            // 保证和上一次枚举的元素不相等
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 使用双指针枚举 b 和 c
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                // 如果和为 target 直接返回答案
                if (sum == target) {
                    return target;
                }
                // 根据差值的绝对值来更新答案
                if (Math.abs(sum - target) < Math.abs(best - target)) {
                    best = sum;
                }
                if (sum > target) {
                    // 如果和大于 target，移动 c 对应的指针
                    int k0 = k - 1;
                    // 移动到下一个不相等的元素
                    while (j < k0 && nums[k0] == nums[k]) {
                        --k0;
                    }
                    k = k0;
                } else {
                    // 如果和小于 target，移动 b 对应的指针
                    int j0 = j + 1;
                    // 移动到下一个不相等的元素
                    while (j0 < k && nums[j0] == nums[j]) {
                        ++j0;
                    }
                    j = j0;
                }
            }
        }
        return best;
    }
import java.lang.reflect.Array;
        import java.util.*;

    public class Test {

        public static List REMOVE(List<String> list){

            List<String> map = new ArrayList<>();
            for (int i = 0; i < list.size(); i++) {
                if (!map.contains(list.get(i))){
                    map.add(list.get(i));//不存在才可以存进map中
                }
            }
            return map;
        }
        public static void main1(String[] args) {
            List<String> list = new ArrayList<>();
            list.add("apple");
            list.add("banana");
            list.add("apple");
            list.add("orange");
            list.add("banana");
            list.add("grape");
            list.add("grape");
            System.out.println(REMOVE(list));


        }

        public static Map<String,Integer> cotain(List<String> list){

            Map<String,Integer> countMap = new HashMap<>();
            for ( String tmp: list) {
                countMap.put(tmp,countMap.getOrDefault(tmp,0)+1);

            }
            return countMap;
        }

        public static void main2(String[] args) {
            List<String> list = new ArrayList<>();
            list.add("apple");
            list.add("banana");
            list.add("apple");
            list.add("orange");
            list.add("banana");
            list.add("grape");
            list.add("grape");
            System.out.println("水果出现的数量:" + cotain(list));
        }

        public static Map<String,List<String>> spilt(List<String> list){

            List<String> num = new ArrayList<>();
            List<String> str = new ArrayList<>();

            for (String s:list) {
                if(s.matches("\\d+")){
                    num.add(s);
                }else if(s.matches("[a-zA-Z]+")){
                    str.add(s);
                }
            }
            Map<String , List<String>> result = new HashMap<>();
            result.put("数字列表" , num);
            result.put("字母列表" , str);
            return result;
        }

        public static void main(String[] args) {
            List<String > list = Arrays.asList("123","abc","456","def","789","ghi");
            System.out.println(spilt(list));



        }
        private static int partition(int[] array, int left, int right) {
            int i = left;
            int j = right;
            int pivot = array[left];
            while (i < j) {
                while (i < j && array[j] >= pivot) {
                    j--;
                }
                while (i < j && array[i] <= pivot) {
                    i++;
                }
                swap(array, i, j);
            }
            swap(array, i, left);
            return i;
        }
        public static int gcd(int a,int b){ // 不需要判断a和b的大小
            while(b>0){
                a%=b;b^=a;a^=b;b^=a;
//           while(b^=a^=b^=a%=b);
            }
            return a;
//        return (a % b == 0) ? b : gcd(b, a%b);
        }

        public static void cinInit(){
            cin.wordChars('a', 'z');
            cin.wordChars('A', 'Z');
            cin.wordChars(128 + 32, 255);
            cin.whitespaceChars(0, ' ');
            cin.commentChar('/');
            cin.quoteChar('"');
            cin.quoteChar('\'');
            cin.parseNumbers(); //可单独使用还原数字
        }
        public static int nextInt() throws Exception {
            cin.nextToken();
            return (int) cin.nval;
        }
        public static long nextLong() throws Exception {
            cin.nextToken();
            return (long) cin.nval;
        }
        public static double nextDouble() throws Exception {
            cin.nextToken();
            return cin.nval;
        }
        public static String nextString() throws Exception {
            cin.nextToken();
            return cin.sval;
        }
        public static void closeAll() throws Exception {
            cout.close();
            in.close();
            out.close();
        }

        public static void heapSort(int[] array) {
            int n = array.length;
            for (int i = n / 2 - 1; i >= 0; i--) {
                heapify(array, n, i);
            }
            for (int i = n - 1; i >= 0; i--) {
                int temp = array[0];
                array[0] = array[i];
                array[i] = temp;
                heapify(array, i, 0);
            }
        }
        public static void cinInit(){
            cin.wordChars('a', 'z');
            cin.wordChars('A', 'Z');
            cin.wordChars(128 + 32, 255);
            cin.whitespaceChars(0, ' ');
            cin.commentChar('/');
            cin.quoteChar('"');
            cin.quoteChar('\'');
            cin.parseNumbers(); //可单独使用还原数字
        }
        public static int nextInt() throws Exception {
            cin.nextToken();
            return (int) cin.nval;
        }
        public static long nextLong() throws Exception {
            cin.nextToken();
            return (long) cin.nval;
        }
        public static double nextDouble() throws Exception {
            cin.nextToken();
            return cin.nval;
        }
        public static String nextString() throws Exception {
            cin.nextToken();
            return cin.sval;
        }
        public static void closeAll() throws Exception {
            cout.close();
            in.close();
            out.close();
        }

        public static void heapSort(int[] array) {
            int n = array.length;
            for (int i = n / 2 - 1; i >= 0; i--) {
                heapify(array, n, i);
            }
            for (int i = n - 1; i >= 0; i--) {
                int temp = array[0];
                array[0] = array[i];
                array[i] = temp;
                heapify(array, i, 0);
            }
        }

        private static void heapify(int[] array, int n, int i) {
            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            if (left < n && array[left] > array[largest]) {
                largest = left;
            }
            if (right < n && array[right] > array[largest]) {
                largest = right;
            }
            if (largest != i) {
                int swap = array[i];
                array[i] = array[largest];
                array[largest] = swap;
                heapify(array, n, largest);
            }
        }
        public static void shellSort(int[] array) {
            int n = array.length;
            for (int gap = n / 2; gap > 0; gap /= 2) {
                for (int i = gap; i < n; i++) {
                    int temp = array[i];
                    int j;
                    for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                        array[j] = array[j - gap];
                    }
                    array[j] = temp;
                }
            }
        }





    }
    private static void heapify(int[] array, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }
        if (largest != i) {
            int swap = array[i];
            array[i] = array[largest];
            array[largest] = swap;
            heapify(array, n, largest);
        }
    }
    public static void shellSort(int[] array) {
        int n = array.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int temp = array[i];
                int j;
                for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                    array[j] = array[j - gap];
                }
                array[j] = temp;
            }
        }
    }





}


    private static void heapify(int[] array, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }
        if (largest != i) {
            int swap = array[i];
            array[i] = array[largest];
            array[largest] = swap;
            heapify(array, n, largest);
        }
    }
    public static void shellSort(int[] array) {
        int n = array.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int temp = array[i];
                int j;
                for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                    array[j] = array[j - gap];
                }
                array[j] = temp;
            }
        }
    }
// 枚举 a
        for (int i = 0; i < n; ++i) {
        // 保证和上一次枚举的元素不相等
        if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
        }
        // 使用双指针枚举 b 和 c
        int j = i + 1, k = n - 1;
        while (j < k) {
        int sum = nums[i] + nums[j] + nums[k];
        // 如果和为 target 直接返回答案
        if (sum == target) {
        return target;
        }
        // 根据差值的绝对值来更新答案
        if (Math.abs(sum - target) < Math.abs(best - target)) {
        best = sum;
        }
        if (sum > target) {
        // 如果和大于 target，移动 c 对应的指针
        int k0 = k - 1;
        // 移动到下一个不相等的元素
        while (j < k0 && nums[k0] == nums[k]) {
        --k0;
        }
        k = k0;
        } else {
        // 如果和小于 target，移动 b 对应的指针
        int j0 = j + 1;
        // 移动到下一个不相等的元素
        while (j0 < k && nums[j0] == nums[j]) {
        ++j0;
        }
        j = j0;
        }
        }
        }
        return best;
        }
        }
        }
class Solution {


    public ListNode removeElements(ListNode head, int val) {


        if (head == null) {
            return null;
        }

        ListNode prev = head;
        ListNode tmep = prev;
        ListNode cur = head.next;

        while (cur != null) {
            if (cur.val == val) {
                tmep.next = cur.next;
                cur = cur.next;
            } else {
                tmep = cur;
                cur = cur.next;
            }
        }

        if (prev.val == val) {
            prev = prev.next;
        }
        return prev;
    }

}
    public static void heapSort(int[] array) {
        int n = array.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }
        for (int i = n - 1; i >= 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            heapify(array, i, 0);
        }
    }

    private static void heapify(int[] array, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }
        if (largest != i) {
            int swap = array[i];
            array[i] = array[largest];
            array[largest] = swap;
            heapify(array, n, largest);
        }
    }
//    移除链表元素
//    给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
//
//    输入：head = [1,2,6,3,4,5,6], val = 6
//    输出：[1,2,3,4,5]
class Solution {


    public ListNode removeElements(ListNode head, int val) {


        if (head == null) {
            return null;
        }

        ListNode prev = head;
        ListNode tmep = prev;
        ListNode cur = head.next;

        while (cur != null) {
            if (cur.val == val) {
                tmep.next = cur.next;
                cur = cur.next;
            } else {
                tmep = cur;
                cur = cur.next;
            }
        }

        if (prev.val == val) {
            prev = prev.next;
        }
        return prev;
    }

  }
    public static void heapSort(int[] array) {
        int n = array.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }
        for (int i = n - 1; i >= 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            heapify(array, i, 0);
        }
    }

    private static void heapify(int[] array, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }
        if (largest != i) {
            int swap = array[i];
            array[i] = array[largest];
            array[largest] = swap;
            heapify(array, n, largest);
        }
    }
    public static void shellSort(int[] array) {
        int n = array.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int temp = array[i];
                int j;
                for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                    array[j] = array[j - gap];
                }
                array[j] = temp;
            }
        }
    }





}


private static void heapify(int[] array, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && array[left] > array[largest]) {
        largest = left;
        }
        if (right < n && array[right] > array[largest]) {
        largest = right;
        }
        if (largest != i) {
        int swap = array[i];
        array[i] = array[largest];
        array[largest] = swap;
        heapify(array, n, largest);
        }
        }
public static void shellSort(int[] array) {
        int n = array.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
        int temp = array[i];
        int j;
        for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
        array[j] = array[j - gap];
        }
        array[j] = temp;
        }
        }
        }
// 枚举 a
}


